package graph;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/*
 *@description 课程表
 *@author hkfan
 *@version 1.0
 *@create 2025/6/16 15:36
 */
public class LeetCode_207 {

    @Test
    public void test(){
        System.out.println(canFinish(2,new int[][]{new int[]{1,0}}));
    }

    class Node{
        int value;
        List<Edge> edges;
        int visited;
        int inNum;

        public Node(int value) {
            this.value = value;
            this.edges = new ArrayList<>();
            this.visited = 0;
            this.inNum = 0;
        }
    }

    class Edge{
        Node from;
        Node to;

        public Edge(Node from, Node to) {
            this.from = from;
            this.to = to;
        }
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //1. 定义
        Map<Integer,Node> nodeMap = new HashMap<>();
        //2. 加入map
        for (int i = 0; i < numCourses; i++) {
            nodeMap.put(i,new Node(i));
        }
        //3. node加入边
        for (int i = 0; i < prerequisites.length; i++) {
            Node from = nodeMap.get(prerequisites[i][1]);
            Node to = nodeMap.get(prerequisites[i][0]);
            from.edges.add(new Edge(from,to));
            to.inNum++;
        }
        //4. 遍历入度为0的点
        for (Node node : nodeMap.values()) {
            if (node.visited==0 && node.inNum==0){
                update(node);
            }
        }
        //5. 检查是否有节点未访问
        for (Node node : nodeMap.values()) {
            if (node.visited==0){
                return false;
            }
        }
        return true;
    }

    private void update(Node node) {
        node.visited=1;
        for (Edge edge : node.edges) {
            Node to = edge.to;
            if (to.inNum<=1 && to.visited==0){
                to.inNum--;
                update(to);
            }
            if (to.inNum>1){
                to.inNum--;
            }
        }
    }

}
